package stackAndQueue;


import java.util.Stack;

/**
 * @Author wangtengyu
 * @Create 2018-09-13-9:26 定义两个整数序列，第一个序列是压入栈的序列顺序， 判断第二个序列是不是栈的弹出序列
 * <p>
 * <p>
 * 思路： 抽象的问题具体化 画出图表，分析是与不是的过程。
 * <p>
 * 定义两个栈。popStack定义了弹出序列。第二个栈pushStack 往第二个栈中压入数据，如果压入的数据和popStack.peek()相同 popStack.pop
 * pushStack.pop
 * <p>
 * 压栈序列12345 弹出序列 45321 true 弹出序列45312 false
 *
 *
 * 4532 5321 头尾的特殊情况判断要考虑到
 */
public class pushAndPop {

  private Stack<Integer> popStack = new Stack<>();
  private Stack<Integer> pushStack = new Stack<>();

  public boolean isPopSequece(int[] pushSequence, int[] popSequence) {
    boolean flag = false;
    if (pushSequence == null || popSequence == null || pushSequence.length < 0
        || popSequence.length < 0) {
      return flag;
    }
    if (pushSequence.length < popSequence.length) {
      return flag;
    }

    //将弹出序列压入栈中
    for (int i = popSequence.length - 1; i >= 0; i--) {
      popStack.push(popSequence[i]);
    }

    //第一次的判断操作 假如说是12345和45321 经历过这一波之后
    //pushStack 123
    //popStack 321
    for (int i = 0; i < pushSequence.length; i++) {
      pushStack.push(pushSequence[i]);
      if (pushStack.peek() == popStack.peek()) {
        popStack.pop();
        pushStack.pop();
      }
    }

    //判断剩下的
    while (pushStack.size() > 0) {

      //判断弹出序列小的情况
      if (popStack.size() == 0) {
        break;
      }

      //相等就互相弹，不相等说明不是
      if (pushStack.peek() == popStack.peek()) {
        pushStack.pop();
        popStack.pop();
      } else {
        //多找规律！！！！ 举个实例比对一下 抽象具体化！！！ 针对的 5,3,2这种情况
        pushStack.pop();
      }
    }

    if (popStack.size() == 0) {
      flag = true;
    }

    return flag;
  }


  public static void main(String[] args) {
    pushAndPop pushAndPop = new pushAndPop();
    int[] pushSequence = new int[]{1, 2, 3, 4, 5};
    int[] popSequence = new int[]{4, 5, 3, 2};
    int[] popSequence2 = new int[]{4, 5, 3, 1, 2};

    boolean isPopSequence = pushAndPop.isPopSequece(pushSequence, popSequence);
    if (isPopSequence) {
      System.out.println("是栈的弹出序列");
    } else {
      System.out.println("不是栈的弹出序列");
    }

  }


}
